iT邦幫忙

DAY 15
1

UML學習過程分享-以EA為例系列 第 15

[Day 15]Entity with self-relation by modeling tree

  • 分享至 

  • xImage
  •  

Entity with self-relation when storing hierarchical data,
I will introduce how to store hierarchical data by interval tree
前言
在每個系統裡面,很容易遇到階層式的資料,什麼叫做階層式的資料呢?
例如我們有個Entity叫做Department,這個Entity是有self-relation,如圖所示:

實際的資料則可能長這樣:

而這樣階層式的資料在系統內,很常有一個需求就是要把某個node底下所有node篩選出來,
例如「技術支援處」底下有哪一些相關單位,例如「台北分公司」底下有哪一些部門,諸如此類的資料。

Solution
這邊舉的例子使用樹狀結構來modeling 階層式的資料,
通常遇到這樣的資料,要設計出self-relation的data model,我們最常採用Parent欄位來表示node與node之間的階層關係,如下圖所示:

如何找出node A底下所有node,以這樣的資料結構,程式實作來說,
步驟1:把自己ID記到Array中
步驟2:把資料表中,Parent欄位為自己ID的資料篩選出來
* 2.1:當資料筆數大於0,每一筆資料再呼叫一次步驟1與步驟2
* 2.2:當資料筆數等於0,則結束。

所以要走遍某個node底下所有的node,就需要透過for loop+遞迴的方式來設計,才能將所有node加入清單內。
以上述這個例子來說,程式實際執行過程應為

[1]加入A
[2]尋找Parent為A的資料,找到兩筆(B與F),第一筆B
[3]加入B,尋找Parent為B的資料,找到三筆(C、D、E),第一筆C
[4]加入C,尋找Parent為C的資料,找到0筆。
[5]第二筆D,加入D,尋找Parent為D的資料,找到0筆。
[6]第三筆E,加入E,尋找Parent為E的資料,找到0筆。
[7]第二筆F,加入F,尋找Parent為F的資料,找到0筆。結束。
清單中就有A~F的node,但是這樣的資料一旦龐大,找階層式資料的effort就會爆炸性的擴大。
怎麼解決這樣的問題?我們這邊要使用的是透過interval tree(或稱為range tree)

我們先來看一下圖解:


我們給每個node兩個屬性,分別是下限與上限,下限上限屬性的規則如上圖所示,
有點類似畫圈圈的方式,把整個tree給圈起來。

當資料給定之後,DB應該會像上圖的表格一樣。

接著神奇的事情就這麼發生了,當我們要選定任意一個Node X底下的所有node集合,請跟著我這麼做:

[1]找到X的下限、上限
[2]Select ID Form Table
Where [下限] > X.下限
And [上限] < X.上限
就這樣一行select from+where搞定。以A為例,就尋找table中上下限介於1~12的資料。

什麼?人客想要找end node有哪一些?
沒問題,只要找下限上限差1的資料就可以了。

當新增一個node G在E底下時,邏輯也相當簡單,
我們看下一張圖:

插入新Node Y於X node,
[1]找到X的下限
[2]Y的下限為X下限+1,Y的上限為X下限+2
[3]Table上下限>X.下限的資料,上下限資料都要+2
以上,是透過interval tree來篩選階層式資料的方式,
這只是最陽春的描述,table還可以搭配原本的方式來達到其他效果,例如paper上的圖

結論
沒想到上班之後還能遇到這麼有趣的資料結構,拿來處理這麼常見的需求。
在這邊分享給大家,希望可以引出更多有趣的想法。


上一篇
[Day 14]MDA中的CIM-2
下一篇
[Day 16]EA的圖貼到Word上亂碼問題
系列文
UML學習過程分享-以EA為例30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言